class RangeFreqQuery {
public:
unordered_map<int,vector<int>> hash;
    RangeFreqQuery(vector<int>& arr) {
        for(int i=0;i<arr.size();++i)
        {
            hash[arr[i]].push_back(i);
        }
    }
    
    int lowerbound(vector<int> &pos,int x)
    {
        int left=0,right=pos.size();
        while(left<right)
        {
            int mid=(left+right)>>1;
            if(pos[mid]>=x) right=mid;
            else left=mid+1;
        }
        return left;
    }

    int upperbound(vector<int> &pos,int x)
    {
        int left=0,right=pos.size();
        while(left<right)
        {
            int mid=(left+right)>>1;
            if(pos[mid]<=x) left=mid+1;
            else right=mid;
        }
        return left;
    }

    int query(int left, int right, int value) {
        vector<int> &pos=hash[value];
        int l=lowerbound(pos,left);
        int r=upperbound(pos,right);
        return r-l;
    }
};